The present invention relates to a digital image processing technology, and in particular to an image coding device for coding image data with a high efficiency and an image decoding device for decoding the coded data which has been coded by the image coding device.
Recently, subband coding techniques have been proposed as highly efficient image coding and decoding techniques. Among the subband coding techniques, a technique for decomposing an image into bands as shown in FIG. 16 in which analysis of an input image is carried out by means of a band decomposing filter bank has been generally known as a technique having a high coding efficiency. Such a technique is described by, for example, Fujii and Nomura xe2x80x9cTopics on Wavelet Transformxe2x80x9d, technical report, IEICE, Institute of Electronics, Information and Communication Engineers, IE 92-11(1992).
FIG. 16 shows subband images which are obtained by conducting two dimensional subband decomposition for an input signal three times. A horizontal high frequency and vertical low frequency subband which is obtained by the first decomposition is designated as HL1. A horizontal low frequency and vertical high frequency subband is designated as LH1. A horizontal high frequency and vertical high frequency subband is designated as HH1. Subbands HL2, LH2 and HH2 are obtained as similarly to the foregoing by conducting second two-dimensional subband decomposition for the horizontal low frequency and vertical low frequency subband.
Subband HL3, LH3 and HH3 are obtained similarly to the foregoing by conducting third two-dimensional subband decomposition for the horizontal low frequency and vertical low frequency subband which has been obtained by second decomposition. A horizontal low frequency and vertical low frequency subband at this time is designated as LL3. The filter bank which is used for decomposing band may use a filter bank for wavelet transformation and a subband decomposing synthesizing filter bank and the like. The image which has been decomposed into subbands in such a manner has a hierarchical structure.
As a recent technique having the highest coding efficiency which is capable of adapting to the subband images, a ZTE (Zero Tree Entropy coding) technique using the above-mentioned hierarchical structure has been proposed (ISO/IEC JTC/SC29/WG11/MPEG95/N0441,ISO/IEC JTC1/SC29/WG11/MPEG96/M0637, ISO/IEC JTC1/SC29/WG11/MPEG96/M1539).
Now, the ZTE technique will be described. In the ZTE technique, a block structure which is shown in FIG. 18 is formed by collecting subband coefficients (hereinafter referred to as coefficients) corresponding to the same spacial positions which are linked with each other by arrows as shown in FIG. 17 from the image which has been decomposed in subbands. It has already known that there is a correlation between coefficients which are linked with each other by arrows in FIG. 17 excepting the highest frequency subbands.
The whole relation of the coefficients which are linked with each other by arrows in FIG. 17 is referred to as xe2x80x9ctreesxe2x80x9d. One coefficient of each of the subbands (LH3, HL3, HH3) having a frequency one level higher than that of one coefficient of the lowest frequency subband (LL3) corresponds thereto (for example, a1, a2 and a3 correspond to a0 in FIG. 17). Four coefficients of each of the subbands (LH2, HL2, HH2) having a frequency one level higher than that of each of these coefficients correspond thereto (for example, a10, a11, a12, a13 correspond to a1 in FIG. 17). Sixteen coefficients of each of the subbands (LH1, HL1, HH1) having a frequency one level higher than that of each of four coefficients correspond thereto. Trees with respect to coefficient a0 is shown in FIG. 19. White circle ◯ and solid black circle xe2x97xaf in FIG. 19 denote coefficients in each subband. The trees in upper area comprise coefficients of the subbands having a lower resolution while the trees in lower area comprise coefficients of the subbands having a higher resolution.
In such a tree structure, the coefficients having lower resolution are referred to as xe2x80x9cparentsxe2x80x9d and the coefficients having next higher resolution in the same spacial position as designated by arrows are referred to as xe2x80x9cchildrenxe2x80x9d. In FIG. 19, for example, coefficient a0 is a parent for coefficients a1, a2 and a3, which are in turn children for coefficient a0. Coefficient a1 is a parent for coefficients a10, a11, a12 and a13 and, coefficients a10, a11, a12 and a13 are children for coefficient a1.
All coefficients having higher resolution in the same spacial position which are linked with each other by arrows with respect to one parent are referred to as xe2x80x9cdescendantsxe2x80x9d and all coefficients having a lower resolution in the same spacial position which are linked with each other by arrows with respect to one child are referred to as xe2x80x9cancestorsxe2x80x9d. In FIG. 19, for example, the coefficients encircled with a dotted line are descendants for coefficient al and coefficients a10, a1 and a0 are ancestors for coefficient a100.
Then, the coefficients are quantized in the block basis. Three symbols are assigned to each node of the trees for representing whether the quantization coefficient is zero or non-zero. Definition of the symbol will now be described. The coefficient having the lowest frequency among the coefficients in which one coefficient in a tree is zero and the coefficients of its descendants are all zero is referred to as zero-tree-root (ZTR). Since this coefficient and the coefficients having a higher resolution than that of the former coefficient are all zero at this time, it would be unnecessary to code the coefficients of its descendant if ZTR appear on a tree. When any one coefficient in a tree is not zero, but the coefficients of its descendant are all zero, the coefficient in interest is referred to as valued zero-tree root (VZTR). If there is any one non-zero coefficient in the descendant, its coefficient is referred to as xe2x80x9cValuexe2x80x9d.
White and solid black circles denote the coefficients which the quantizing value is zero and non-zero, respectively in FIG. 19. In this case, the coefficients which require coding are shown in FIG. 20. Since a0 has a quantizing value which is not xe2x80x9czeroxe2x80x9d in FIG. 20, the symbol Value is assigned to code the quantizing value. Since a1 and its descendants (a10 through a13, a100 through a103 through a133) are all zero, symbol ZTR is assigned to a1 and it is not necessary to code the quantizing value. Since it can be found that the value of a1 is zero due to the fact that a1 is ZTR, it is never necessary to code the information on the descendants of a1.
Since a2 has a quantizing value which is not zero, but its descendants all have a quantizing value which is zero, symbol VZTR is assigned for coding only the quantizing value of a2. Concerning the descendants of a2, same as those of a1, it is not necessary to code their information. Since a3 has a quantizing value which is not zero and there are some descendants which have a quantizing value which is not zero, symbol Value is assigned for coding the quantizing value. VZTR is assigned for a30. ZTR is assigned for a31. Value is assigned for a32 and a33. Only the quantizing values of the coefficients having the highest frequency (a320 through a333) are coded without assigning a symbol to the coefficients. As mentioned above, the information to be coded on this block comprises:
symbol information including Value, ZTR, VZTR, Value, VZTR, ZTR, Value, Value, Value, Value, Value, . . . , Value and coefficient information including Q(a0), Q(a2), Q(a3),
Q(a30), Q(a32), Q(a33), Q(a320), Q(a321), Q(a322), . . . , Q(a333), wherein Q(a) denotes the quantizing value of the coefficient a. The contents of coded data are shown in FIG. 21.
When the symbol is VZTR or Value, it is necessary to code the quantizing values of the coefficients. Since there are generally a lot of coefficients having a quantizing value which is zero in the high frequency subband, many ZTRs are generated so that it is unnecessary to code the coefficient value. Therefore high coding efficiency is achieved.
As mentioned above, in the ZTE technique the order of coding of the coefficients does not shift subband by subband, but quantization of each block is conducted, then the symbol information and the coefficient information in the block basis is completely coded and thereafter coding of next block is initiated.
An image coding device using the ZTE technique is shown in FIG. 14 and an image decoding device using the ZTE technique is shown in FIG. 15. In FIG. 14, a reference numeral 1401 denotes a subband decomposing portion for decomposing an image into subbands by means of a two-dimensional decomposing filter, 1402 denotes a block forming portion for forming a block by collecting coefficients having a parent-child relationship from the decomposed subbands as shown in FIG. 18, 1403 denotes a quantizing portion for quantizing the coefficients in the block basis, 1404 denotes a symbol information determining portion for determining the symbol which is shown in FIG. 20 in the block basis from the coefficients after the quantization, 1405 denotes a symbol information coding portion for variable-length coding each symbol information, 1406 denotes a coefficient coding portion for coding only the coefficients in which the symbol information which is determined in portion 1404 corresponds to VZTR or Value, and 1407 denotes a data integrating portion for integrating to array the symbol information before the coefficient information in one block. FIG. 22 is a flow chart showing a series of the operations.
In FIG. 15, a reference numeral 1501 denotes a data separating portion for separating coded data into symbol information and coefficient information for each one block, 1502 denotes a symbol information decoding portion for variable-length decoding symbol information, 1503 denotes a coefficient decoding portion for decoding the coefficients corresponding to Value and VZTR based upon the decoded symbol information, 1504 denotes a block data reproducing portion for reproducing all coefficient values for one block based upon the decoded symbol information and coefficient information, 1505 denotes an inverse quantizing portion for inverse quantizing the quantized coefficients for each block, 1506 denotes a subband image producing portion for producing the whole subband image by relocating the coefficient values of all blocks to deblocking them, and 1507 denotes a subband synthesizing portion for performing a subband synthesis by means of a two-dimensional synthesizing filter. FIG. 23 is a flow chart showing a series of operations.
The subband coefficients can be efficiently coded and decoded in the block basis by using the above-mentioned image coding and decoding devices.
Since a block in which subband coefficients having a parent-child relationship are collected is formed and coded in the ZTE technique in such a manner, quantization in the block basis is possible. The coding efficiency can be improved by using a fact that most of the coefficients of the high frequency are zero. On the contrary, the coded data can not be provided with the scalability which the subband coding inherently possesses.
In other words, reproduced images having different resolutions can be decoded from part of the coded data as shown in FIG. 24 in the conventional subband coding technique in which information on one subband is coded and then the information on the subband having the next higher resolution is coded. If for example, the information on only LL3 is decoded from the coded data, the whole image could be reproduced at the lowest resolution.
If LL3, HL3, LH3 and HH3 among the coded data are decoded, the whole image can be reproduced at a resolution which is higher than the case of decoding of only LL3. If all coded data is decoded, the whole image can be reproduced at the highest resolution.
However, in the ZTR technique, quantization in the block basis is possible and the coding efficiency can be improved by using the fact that most of the coefficients of the high frequency subband is zero. But if some of the coded data is decoded from the left and upper area of an image in the block basis, only part of the image can be reproduced although the regenerated part has a high resolution. In other words, the scalability which the subband inherently has is lost in the ZTE technique.
In order to overcome the above-mentioned problems,
(1) The present invention provides an image coding device comprising means for decomposing an image into subbands to produce a first subband image; means for forming a blocked second subband image by collecting subband coefficients having a parent-child relationship between subbands in said first subband image to form a plurality of blocks; means for quantizing said subband coefficients of each block of said second subband image; means for determining symbol information representing whether the quantized subband coefficient of said second subband image is xe2x80x9c0xe2x80x9d or non xe2x80x9c0xe2x80x9d; means for relocating the symbol information of said second subband image in accordance with the frequency position in said first subband image; means for variable-length coding said relocated symbol information; means for relocating said quantized subband coefficients to be coded based upon said symbol information and forming a third subband image in accordance with the frequency position in said first subband image; means for variable-length coding said relocated subband coefficients; and means for collecting and arranging said coded symbol information and subband coefficients in each subband.
(2) The present invention comprises: means for separating said coded data into symbol information and subband coefficients; means for decoding said coded symbol information for each subband; means for reproducing said third subband image by decoding each of said subband coefficient based upon said decoded symbol information; means for forming said second blocked subband image comprising a plurality of blocks which are formed by collecting said decoded subband coefficients having a parent-child relationship in each subband; means for inverse quantizing said decoded subband coefficients of said second subband image; means for producing subband images which are relocated in accordance with the frequency position in said third subband coefficient by deblocking said inverse quantized subband coefficients of said second subband image; and means for synthesizing said subband images to provide a decoded image.
(3) There is provided means for arranging firstly all pieces of said symbol information in each subband and then arranging all said subband coefficients in each subband when said coded symbol information and subband coefficients are collected into one group for each subband.
(4) There is provided means for conducting an operation for separating the coded data which is one group comprising the symbol information and subband coefficients which are collected for each subband into all pieces of said symbol information in one subband firstly, and then into all said subband coefficient information in one subband.
(5) There is provided means for arranging sets of said symbol information and said subband coefficient corresponding thereto in accordance with the order of said symbol information in each subband, when said coded symbol information and subband coefficients are collected into one group for each subband.
(6) There is provided means for conducting an operation for separating the coded data which is one group comprising the symbol information and subband coefficients which are collected for each subband into said symbol information and said subband coefficient for each symbol for all subbands in said coded data.
(7) In lieu of said symbol information coding portion, said coefficient information coding portion and said coded data integrating portion, there are provided means for forming a set of the symbol information and subband coefficient corresponding to said symbol information, and means for variable-length coding said set of said symbol information and subband coefficient information.
(8) In lieu of said decoded data separating portion, said symbol information decoding portion and said coefficient information decoding portion, there are provided means for decoding a set of said symbol information and subband coefficient information and means for separating said decoded set into symbol information and coefficient information.
(9) There is provided means for inserting xe2x80x9c0xe2x80x9d into the subband coefficient value which can not be decoded if complete coded data which is produced by said image coding device can not be inputted.